#Pyton library imports
import re
#External libraries imports
from pyparsing import *
#Internal imports
from Exceptions import SyntacticException, SemanticException
from ParsingUtilities import *
from FSPExpressionParser import ExpressionParser

def FSPSyntaxChecker(FSPSource):

  definitionsDictionary = {}
  definitionsTypes = {"set":[], "const":[], "range": [], "process":[]}
  dependencyGraph = {}
  processBuffer = []
  referencedButUndefined = set()

  def addDefinition(x, definitionId, FSPType):
    x = x.asList()
    nonlocal definitionsDictionary
    nonlocal definitionsTypes
    nonlocal dependencyGraph
    nonlocal processBuffer
    if definitionId not in definitionsDictionary:
      definitionsDictionary[definitionId] = strJoin(x)
      definitionsTypes[FSPType] = definitionId
      if FSPType == "process":
        processBuffer.append(definitionId)
        return x
      if definitionId in referencedButUndefined:
        referencedButUndefined.remove(definitionId)
      else:
        dependencyGraph[definitionId] = []
    else:
      raise SemanticException(
        "Global namespace", 0, definitionId + ": found conflicting definition.")
    for i in range(0, len(x)):
      if x[i] != definitionId\
      and re.match("^"+uppercaseRegex+"$", x[i])\
      and not re.match("^(STOP|END|ERROR)$", x[i]):
        if x[i] not in definitionsDictionary:
          referencedButUndefined.add(x[i])
          if x[i] not in dependencyGraph: dependencyGraph[x[i]] = []
        if definitionId not in dependencyGraph[x[i]]:
          dependencyGraph[x[i]].append(definitionId)
    return x

  Expression = ExpressionParser(namespace=None, justCheck=True)

  ConstantDefinition = (
    Keyword("const") + UppercaseIdentifier + Literal("=") + Expression
    ).setParseAction(lambda x: addSpace(x, 1), lambda x: addDefinition(x, x[2], "const"))

  RangeExpression = Expression + Literal("..") + Expression

  RangeDefinition = (
    Keyword("range") + UppercaseIdentifier + Literal("=") + RangeExpression
    ).setParseAction(lambda x: addSpace(x, 1), lambda x: addDefinition(x, x[2], "range"))

  Range = UppercaseIdentifier ^ RangeExpression

  ActionLabels = Forward()

  SetElements = ActionLabels + ZeroOrMore(Literal(",") + ActionLabels)

  SetExpression = Literal("{") + SetElements + Literal("}")

  SetDefinition = (
    Keyword("set") + UppercaseIdentifier + Literal("=") + SetExpression
    ).setParseAction(lambda x: addSpace(x, 1), lambda x: addDefinition(x, x[2], "set"))

  Set = UppercaseIdentifier ^ SetExpression

  ActionLabel = (
      (LowercaseIdentifier ^ (Literal("[") + Expression + Literal("]"))) +
      ZeroOrMore
        (
          (Literal(".") + LowercaseIdentifier)
          ^
          (Literal("[") + Expression + Literal("]"))))

  VariableDefinition = (LowercaseIdentifier + Literal(":") +
    (UppercaseIdentifier ^ RangeExpression ^ SetExpression))

  ActionRange = (
    UppercaseIdentifier ^ SetExpression ^ RangeExpression ^ VariableDefinition)

  ActionLabels << (
    (ActionLabel ^ Set ^ (Literal("[") + ActionRange + Literal("]"))) +
    ZeroOrMore(
      (Literal(".") + (ActionLabel ^ Set)) ^
      (Literal("[") + ActionRange + Literal("]")) ^
      Combine(Literal("[") + Expression + Literal("]"))))

  Choice = Forward()

  PrefixActions = ActionLabels + ZeroOrMore(Literal("->") + (ActionLabels^(Literal("(") + Choice + Literal(")"))))

  Guard = (Keyword("when") + Expression).setParseAction(lambda x: x.insert(1, " "))

  LocalProcess = Forward()

  ActionPrefix = (Optional(Guard) + PrefixActions)#NB: this grammar is incorrect, there should be ->LocalProc
  #However, that production is ambiguous! This production accepts
  #as prefix action prefixes both a->H and a->{a,b}, which is illegal!
  #each action prefix must end with a local process! This ambiguity is treated
  #in the next compilation step

  Indices = OneOrMore(Literal("[") + Expression + Literal("]"))

  IndexRanges = OneOrMore(Literal("[") + (Expression ^ ActionRange) + Literal("]"))

  ParameterDefinition = UppercaseIdentifier + Literal("=") + Expression

  Parameters = (Literal("(") +
    ParameterDefinition + ZeroOrMore(Literal(",") + ParameterDefinition) +
    Literal(")"))

  BaseLocalProcess = (
    (Keyword("END") ^ Keyword("STOP") ^ Keyword("ERROR"))
    .setParseAction(lambda x: addSpace(x, 1)) ^
    (UppercaseIdentifier + Optional(Indices)))

  Choice << ActionPrefix + ZeroOrMore(Literal("|") + ActionPrefix)

  LocalProcess << (
    BaseLocalProcess ^
    #SequentialComposition ^
    #if Expression then LocalProcess ^
    #if Expression then LocalProcess else LocalProcess ^
    (Literal("(") + Choice + Literal(")")))

  LocalProcessDefinition = (
    UppercaseIdentifier + Optional(IndexRanges) + Literal("=") + LocalProcess)

  ProcessBody = (
    LocalProcess + ZeroOrMore(Literal(",") + LocalProcessDefinition))

  AlphabetExtension = (Literal("+") + Set)

  RelabelRule = ActionLabels + Literal("/") + ActionLabels
  #oppure forall IndexRanges { RelabelDefs }

  RelabelRules = RelabelRule + ZeroOrMore(Literal(",") + RelabelRule)

  Relabel = Literal("/") + Literal("{") + RelabelRules + Literal("}")

  SelectiveExposition = Literal("@") + Set

  SelectiveHiding = Literal("\\") + Set

  Hiding = SelectiveHiding ^ SelectiveExposition

  ProcessDefinition = (
    UppercaseIdentifier + Optional(Parameters) + Literal("=") +
    ProcessBody + Optional(AlphabetExtension) + Optional(Relabel) +
    Optional(Hiding) + Literal(".")).setParseAction(lambda x: addDefinition(x, x[0], "process"))

  Definitions = ZeroOrMore(ConstantDefinition|RangeDefinition|SetDefinition|ProcessDefinition)

  def cycles(graph):
    result = []
    stack = []
    low = {}
    def visit(node):
      if node in low: return
      num = len(low)
      low[node] = num
      stack_pos = len(stack)
      stack.append(node)
      for successor in graph[node]:
        visit(successor)
        low[node] = min(low[node], low[successor])
      if num == low[node]:
        component = list(stack[stack_pos:])
        del stack[stack_pos:]
        if len(component) > 1: result.append(component)
        for item in component:
          low[item] = len(graph)
    for node in graph:
      visit(node)
    return result

  def topologicalSort(graph):
    referenceCount = {}
    for node in graph:
      referenceCount[node] = 0
    for node in graph:
      for successor in graph[node]:
        referenceCount[successor] += 1
    satisfiedNodes = [n for n in graph if referenceCount[n] == 0]
    for node in satisfiedNodes:
      yield node
      for successor in graph[node]:
        referenceCount[successor] -= 1
        if referenceCount[successor] == 0:
          satisfiedNodes.append(successor)

  def sortDefinitions(graph):
    nonlocal processBuffer
    for definition in topologicalSort(graph):
        yield definition
    for process in processBuffer: yield process


  """GENERATOR CODE"""
  Definitions.parseString(FSPSource, parseAll=True)
  if referencedButUndefined:
    raise SemanticException("Global namespace", 0, str(referencedButUndefined) + ": undefined symbols used.")
  dependencyCycles = cycles(dependencyGraph)
  if dependencyCycles:
    raise SemanticException("", 0, "Dependency cycles detected: " + str(dependencyCycles))
  #print("DEPENDENCY GRAPH:", dependencyGraph)
  for definition in sortDefinitions(dependencyGraph):
    yield definitionsDictionary[definition]
    del definitionsDictionary[definition]
